Information that is used to access a stored digital item is referred to herein as the “access key” of the stored item. In typical file systems, stored items are retrieved based on (a) the location at which the items are stored, and (b) a name or identifier of the items. For example, if a file named “foo.txt” is located in a directory named “c:\myfiles\text”, then applications may use the pathname “c:\myfiles\text\foo.txt” as the access key to retrieve the file from the file system. Because conventional access keys are based on the location of the items being retrieved, the access keys change when the items are moved. In addition, each copy of an item has a different access key, because each copy is stored at a different location.
In contrast to conventional file systems, Content Addressable Storage (CAS) systems allow applications to retrieve items from storage based on a hash value that is generated from the content of the items. Because CAS systems perform storage-related operations on items based on the hash values generated for the items, and the hash values are based on the content of the items rather than where the items are stored, the applications that request the operations may do so without knowing the number or location of the stored copies of the items. For example, a CAS system may store multiple copies of an item X at locations A, B and C. An application that desires to retrieve item X would do so by sending to the CAS system a hash value that is based on the contents of item X. Based on that hash value, the CAS system would provide to the application a copy of item X retrieved from one of the locations A, B, and C. Thus, the application would obtain item X without knowing where item X was actually stored, how many copies of item X existed, or the specific location from which the retrieved copy was actually obtained.
Storing a digital item, such as a file or a message, often involves making a call to a “chunk storage system” or “chunk store”. A chunk storage system is a storage system that performs storage operations without understanding the format or content of the digital information itself. Such storage systems are referred to as chuck storage systems or chunk stores because the systems treat all forms of digital items as if those items were merely opaque chunks of data. For example, the same chunk storage system may be used by word processing applications, image management applications, and calendaring systems to respectively store documents, images and appointments. However, from the perspective of the chunk storage system, only one type of item is being stored: opaque chunks of digital information.
Chunk storage systems may be implemented as CAS systems. For example, a chunk storage system may generate a hash value for a chunk by applying a cryptographic hash function (e.g. MD5, SHA-1 or SHA2) to the chunk. The chunk store may then store the chunk, and maintain an index that associates the hash value with the location at which the chunk is stored. When an application subsequently requests retrieval of the chunk, the application provides the hash value to the chunk storage system. The chunk storage system uses the index to locate the chunk associated with the hash value, and provides the chunk thus located to the requesting application.
Chunks may be used to represent a file system hierarchy, where some chunks correspond to folders/directories of the file system hierarchy, and other chunks correspond to files that are stored in those folders/directories. FIG. 1 illustrates such a hierarchy. The hierarchical relationship illustrated in FIG. 1 has two non-overlapping trees, one of which is rooted at chunk 104, and the other of which is rooted at chunk 106. However, it is also possible for any given chunk or sub-tree of chunks to belong to multiple trees within the hierarchy. A hierarchical arrangement in which any given node (e.g. chunk) may belong to multiple trees is referred to as a Direct Acyclic Graph (“DAG”). The techniques described herein are equally applicable to chunk stores that represent DAG hierarchies as chunk stores that represent non-overlapping tree hierarchies.
Referring to FIG. 1, it illustrates a file system hierarchy implemented by chunks. In FIG. 1, the chunks are arranged in a manner that reflects the hierarchical relationship between the files represented by the chunks. For example, in the hierarchy, a file B resides in the directory “PPTS” which is a child of the directory “DOCS”, which in turn is a child of the directory “JACK”, which is the root directory for Jack's account. Consequently, the chunk 122 that corresponds to File B is shown as a child of chunk 116 that corresponds to directory “PPTS”. Similarly, chunk 116 is shown as a child of chunk 114 that corresponds to directory “DOCS”, chuck 114 is shown as a child of chunk 104 that corresponds to root directory “JACK”.
While the arrangement of chunks in FIG. 1 reflects the hierarchical relationship between the files to which the chunks correspond, the actual arrangement of the chunks within a chunk store may have no relationship to that hierarchy. For example, the chunks may be randomly distributed across several storage devices. Thus, the arrangement illustrated in FIG. 1 is merely to facilitate understanding of the techniques described herein.
When a file system hierarchy is implemented using a chunk store, the addition or modification of a single file may necessitate changes to every file that is above that file in the hierarchy. Specifically, because the files are implemented by chunks that are addressed based on content, the modification of the single file causes creation of new chunks for every file that is above the file in the hierarchy.
For example, assume that a user updates file B, represented by chunk 122. Because the update to file B changes the content of the chunk, and chunks are addressed based on content, the new chunk is not simply stored over the chunk 122 that had the prior version of file B. Rather, the modified version of file B constitutes a new chunk, which is stored separate from chunk 122.
FIG. 2 is a block diagram that illustrates the new chunks that are produced in response to the update to file B. Referring to FIG. 2, the new version of file B is stored in chunk 222. Because File B is stored in a new chunk, the chunk 116 that corresponds to the directory “PPTS” in which File B resides must also be updated to point to the new chunk 222 for File B. The updated file for the directory “PPTS” is stored as chunk 216. Similarly, the chunk 114 that corresponds to the directory “DOCS” that is the parent of “PPTS” must also be updated to point to the new chunk for the “PPTS” directory. The updated file for “DOCS” is stored as chunk 214. For similar reasons, a new chunk 204 is stored for the root directory “JACK” that is the parent of “DOCS”.
As a consequence of the update to file B, several chunks have become “stale”. A stale chunk is a chunk whose data no longer reflects the current state of the file system. In the example given above, the update to file B causes chunks 104, 114, 116 and 122 to become stale. The more updates that are performed, the more chunks become stale.
When a chunk store is used to implement a hierarchical file system, a name store may be used to maintain an association between each file name and the hash of the chunk that currently represents the file. For example, prior to the update to file B, the name store would include the following associations:                “JACK”=>hash of chunk 104        “DOCS”=>hash of chunk 114        “PPTS”=>hash of chunk 116        “FILE B”=>hash of chunk 122        
After the update to file B, the name store would include the following associations:                “JACK”=>hash of chunk 204        “DOCS”=>hash of chunk 214        “PPTS”=>hash of chunk 216        “FILE B”=>hash of chunk 222        
Because the name store only points to the chunks that correspond to the most recent versions of files, some stale chunks may become unused. The process of identifying which chunks are stale, and then recovering the space those stale chunks occupy so that it may be reused, is referred to as garbage collection (GC). Given the rate at which stale chunks may proliferate when a chunk store is used as a file system, it is critical that the garbage collection process used by the chunk store be fast and efficient.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.